

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/resource/img/favicon.png">
  <link rel="icon" type="image/png" href="/resource/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="soldier">
  <meta name="keywords" content="">
  <title>排序算法学习笔记 - 黄结的个人博客</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/github-gist.min.css" />
    
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.2.0"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>soldier</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item dropdown">
              <a class="nav-link dropdown-toggle" href="#" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
              <div class="dropdown-menu" aria-labelledby="navbarDropdown">
                
                  
                  
                  
                  <a class="dropdown-item" href="/about/">
                    
                    个人简历
                  </a>
                
                  
                  
                  
                  <a class="dropdown-item" target="_blank" rel="noopener" href="https://soldiergit.github.io/honor/">
                    
                    项目及获奖
                  </a>
                
              </div>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-11-24 11:20" pubdate>
        2020年11月24日 上午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      4.4k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      57
       分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">排序算法学习笔记</h1>
            
            <div class="markdown-body" id="post-body">
              <h2 id="约定"><a href="#约定" class="headerlink" title="约定"></a>约定</h2><p><strong>提取每一个排序算法公共部分作为父类的属性</strong>：<br>待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。<br>使用辅助函数 less() 和 swap() 来进行比较的交换的操作，使得代码的可读性和可移植性更好。</p>
<p>排序算法的成本模型是比较和交换的次数。</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-keyword">abstract</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; </span>&#123;

    <span class="hljs-comment">// 具体排序实现</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">abstract</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span></span>;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 比较</span>
<span class="hljs-comment">     * 小于返回true；大于返回false</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">protected</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">less</span><span class="hljs-params">(T v, T w)</span> </span>&#123;
        <span class="hljs-comment">// compareTo--&gt;小于返回-1；等于返回0；大于返回1</span>
        <span class="hljs-keyword">return</span> v.compareTo(w) &lt; <span class="hljs-number">0</span>;
    &#125;

    <span class="hljs-comment">// 交换</span>
    <span class="hljs-function"><span class="hljs-keyword">protected</span> <span class="hljs-keyword">void</span> <span class="hljs-title">swap</span><span class="hljs-params">(T[] a, <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>&#123;
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    &#125;
&#125;</code></pre>

<h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><p><font color=#FF000><strong>概念</strong></font>：从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。</p>
<p>选择排序需要 ~N<sup>2</sup>/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。</p>
<p><strong>实现</strong>：</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Selection</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        <span class="hljs-comment">// 数组长度</span>
        <span class="hljs-keyword">int</span> n = nums.length;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n -<span class="hljs-number">1</span>; i++) &#123;
            <span class="hljs-comment">// 取数组第1个到 n-1 个元素</span>
            <span class="hljs-keyword">int</span> min = i;
            <span class="hljs-comment">// 与子数组进行比较</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i + <span class="hljs-number">1</span>; j &lt; n; j++) &#123;
                <span class="hljs-comment">// 获取最小元素下标</span>
                <span class="hljs-keyword">if</span> (less(nums[j], nums[min])) min = j;
            &#125;
            <span class="hljs-comment">// 把最小的元素放到前面</span>
            swap(nums, i, min);
        &#125;
    &#125;
&#125;</code></pre>

<h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><p><font color=#FF000><strong>概念</strong></font>：从左到右不断比较相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生变化，那么说明数组已经是有序的，此时可以直接退出。</p>
<p><strong>实现</strong>：</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Bubble</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        <span class="hljs-comment">// 数组长度</span>
        <span class="hljs-keyword">int</span> n = nums.length;
        <span class="hljs-keyword">boolean</span> isSorted = <span class="hljs-keyword">false</span>;
        <span class="hljs-comment">// 取游标i：从最后一个元素取到第二个元素，游标后的元素已经有序</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = n - <span class="hljs-number">1</span>; i &gt; <span class="hljs-number">0</span> &amp;&amp; !isSorted; i--) &#123;
            <span class="hljs-comment">// 每取一次都默认当前数组已经有序</span>
            isSorted = <span class="hljs-keyword">true</span>;
            <span class="hljs-comment">// 只比较游标前的元素</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; i; j++) &#123;
                <span class="hljs-comment">// 某相邻的两个元素不是有序</span>
                <span class="hljs-keyword">if</span> (less(nums[j + <span class="hljs-number">1</span>], nums[j])) &#123;
                    <span class="hljs-comment">// 表明这个数组还不是有序的</span>
                    isSorted = <span class="hljs-keyword">false</span>;
                    <span class="hljs-comment">// 交换相邻两个元素位置</span>
                    swap(nums, j, j + <span class="hljs-number">1</span>);
                &#125;
            &#125;
        &#125;
    &#125;
&#125;</code></pre>

<h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><p><font color=#FF000><strong>概念</strong></font>：每次都将当前元素插入到左侧以及排序的数组中，使得插入之后左侧数组依然有序。</p>
<p>对于数值{3, 5, 2, 4, 1}，它具有一下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少1，因此插入排序需要交换的次数为逆序数量。</p>
<p>插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。</p>
<ul>
<li>平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；</li>
<li>最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；</li>
<li>最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。</li>
</ul>
<p><strong>实现</strong>：</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Insertion</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        <span class="hljs-comment">// 数组长度</span>
        <span class="hljs-keyword">int</span> n = nums.length;
        <span class="hljs-comment">// 游标i：从第二个元素开始取</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; n; i++) &#123;
            <span class="hljs-comment">// 从游标处倒着比较到第1个元素，比较并交换相邻两个元素；有序时直接跳过</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i; j &gt; <span class="hljs-number">0</span> &amp;&amp; less(nums[j], nums[j - <span class="hljs-number">1</span>]); j--) &#123;
                swap(nums, j, j - <span class="hljs-number">1</span>);
            &#125;
        &#125;
    &#125;
&#125;</code></pre>

<h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><p><font color=#FF000><strong>概念</strong></font>：对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过<strong>交换不相邻的元素</strong>，每次可以将逆序数量减少大于1.</p>
<p>希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减少 h，最后令 h=1，就可以使得整个数组是有序的。<br><img src="/resource/img/java/Sort_shell.png" srcset="/img/loading.gif"></p>
<p><strong>实现</strong>：</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Shell</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        <span class="hljs-comment">// 数组长度</span>
        <span class="hljs-keyword">int</span> n = nums.length;

        <span class="hljs-comment">// 计算递增序列h：1, 4, 13, 40, 121, 364, 1093...(间隔为1时是插入排序)</span>
        <span class="hljs-keyword">int</span> h = <span class="hljs-number">1</span>;
        <span class="hljs-keyword">while</span> (h &lt; n / <span class="hljs-number">3</span>) &#123;
            h = <span class="hljs-number">3</span> * h + <span class="hljs-number">1</span>;
        &#125;

        <span class="hljs-comment">// 通过while循环，每次减少3倍序列h的值</span>
        <span class="hljs-keyword">while</span> (h &gt;= <span class="hljs-number">1</span>) &#123;
            <span class="hljs-comment">// 使用插入排序对间隔 h 的数组进行排序</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = h; i &lt; n; i++) &#123;
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i; j &gt;= h &amp;&amp; less(nums[j], nums[j - h]) ; j -= h) &#123;
                    swap(nums, j, j-h);
                &#125;
            &#125;
            h /= <span class="hljs-number">3</span>;
        &#125;
    &#125;
&#125;</code></pre>
<p>希尔排序的运行时间达不到平方级别，使用<code>递增序列 1, 4, 13, 40, ...</code> 的希尔排序所需要的比较次数不会超过 <code>n 的若干倍</code>乘于 <code>递增序列的长度</code>。后面介绍的高级排序算法只会比希尔排序快两倍左右。</p>
<h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><p><font color=#FF000><strong>概念</strong></font>：是将数组分成两部分，分别进行排序，然后归并起来。<br><img src="/resource/img/java/Sort_merge.png" srcset="/img/loading.gif"></p>
<h3 id="1-公共的归并方法"><a href="#1-公共的归并方法" class="headerlink" title="1.公共的归并方法"></a>1.公共的归并方法</h3><p><strong>归并方法</strong>将数组中两个已经排序的部分归并成一个。它基础自约定Sort类，是两种类型的归并排序的父类，内含公共的合并方法。</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-keyword">abstract</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MergeSort</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;

    <span class="hljs-comment">// 辅助数组</span>
    <span class="hljs-keyword">protected</span> T[] aux;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 将数组中两个已经排序的部分归并成一个，l和h表明起始位置</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> nums  被操纵数组</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> l     数组下标开始位置</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> m     数组中间下标</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> h     数组下标结束位置</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">protected</span> <span class="hljs-keyword">void</span> <span class="hljs-title">merge</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> m, <span class="hljs-keyword">int</span> h)</span> </span>&#123;
        <span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>, j = m+<span class="hljs-number">1</span>;

        <span class="hljs-comment">// 将数据复制到辅助数组</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = l; k &lt;= h; k++) &#123;
            aux[k] = nums[k];
        &#125;

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = l; k &lt;= h; k++) &#123;
            <span class="hljs-keyword">if</span> (i &gt; m) &#123;
                nums[k] = aux[j++];
            &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (j &gt; h) &#123;
                nums[k] = aux[i++];
            &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (aux[i].compareTo(aux[j]) &lt;= <span class="hljs-number">0</span>) &#123;
                <span class="hljs-comment">// compareTo--&gt;小于返回-1；等于返回0；大于返回1</span>
                nums[k] = aux[i++]; <span class="hljs-comment">// 先进行这一步，保证稳定性</span>
            &#125; <span class="hljs-keyword">else</span> &#123;
                nums[k] = aux[j++];
            &#125;
        &#125;
    &#125;
&#125;</code></pre>

<h3 id="2-自顶向下的归并排序"><a href="#2-自顶向下的归并排序" class="headerlink" title="2.自顶向下的归并排序"></a>2.自顶向下的归并排序</h3><p>将一个大数组分成两个小数组去求解。</p>
<p>因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为：O(NlogN)。</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Up2DownMergeSort</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">MergeSort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        aux = (T[]) <span class="hljs-keyword">new</span> Comparable[nums.length];
        sort(nums, <span class="hljs-number">0</span>, nums.length - <span class="hljs-number">1</span>);
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 排序</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> nums  被操纵数组</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> l     数组下标开始位置</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> h     数组下标结束位置</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> h)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (h &lt;= <span class="hljs-number">1</span>) <span class="hljs-keyword">return</span>;
        <span class="hljs-comment">// 计算当前数组中间下标</span>
        <span class="hljs-keyword">int</span> mid = <span class="hljs-number">1</span> + (h-<span class="hljs-number">1</span>) / <span class="hljs-number">2</span>;
        <span class="hljs-comment">// 递归：排序左子数组</span>
        sort(nums, l, mid);
        <span class="hljs-comment">// 递归：排序右子数组</span>
        sort(nums, mid + <span class="hljs-number">1</span>, h);
        <span class="hljs-comment">// 根据中间下标，合并左右子数组</span>
        merge(nums, l ,mid, h);
    &#125;
&#125;</code></pre>

<h3 id="3-自底向上的归并排序"><a href="#3-自底向上的归并排序" class="headerlink" title="3.自底向上的归并排序"></a>3.自底向上的归并排序</h3><p>先归并那些微型数组，然后成对归并得到的微型数组。</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Down2UpMergeSort</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">MergeSort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        <span class="hljs-keyword">int</span> n = nums.length;
        aux = (T[]) <span class="hljs-keyword">new</span> Comparable[n];

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> sz = <span class="hljs-number">1</span>; sz &lt; n; sz += sz) &#123;
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> lo = <span class="hljs-number">0</span>; lo &lt; n - sz; lo += sz + sz) &#123;
                merge(nums, lo, lo + sz - <span class="hljs-number">1</span>, Math.min(lo + sz + sz - <span class="hljs-number">1</span>, n - <span class="hljs-number">1</span>));
            &#125;
        &#125;
    &#125;
&#125;</code></pre>

<h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><h3 id="1-基本算法"><a href="#1-基本算法" class="headerlink" title="1.基本算法"></a>1.基本算法</h3><p><font color=#FF000><strong>概念</strong></font>：</p>
<ul>
<li>归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；</li>
<li>快速排序通过一个切分元素将数组分为两个子数组，左子数组小于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。</li>
</ul>
<p><img src="/resource/img/java/Sort_quick.png" srcset="/img/loading.gif"></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">QuickSort</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        shuffle(nums);
        sort(nums, <span class="hljs-number">0</span>, nums.length - <span class="hljs-number">1</span>);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">protected</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> h)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (h &lt;= <span class="hljs-number">1</span>) <span class="hljs-keyword">return</span>;
        <span class="hljs-keyword">int</span> j = partition(nums, l, h);
        sort(nums, l, j - <span class="hljs-number">1</span>);
        sort(nums, j + <span class="hljs-number">1</span>, h);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">shuffle</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        List&lt;Comparable&gt; list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    &#125;
&#125;</code></pre>
<h3 id="2-切分"><a href="#2-切分" class="headerlink" title="2.切分"></a>2.切分</h3><p>将 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。<br><img src="/resource/img/java/Sort_partition.gif" srcset="/img/loading.gif"></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">partition</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> h)</span> </span>&#123;
    <span class="hljs-keyword">int</span> i = l, j = h + <span class="hljs-number">1</span>;
    T v = nums[l];
    <span class="hljs-keyword">while</span> (<span class="hljs-keyword">true</span>) &#123;
        <span class="hljs-keyword">while</span> (less(nums[++i], v) &amp;&amp; i != h) ;
        <span class="hljs-keyword">while</span> (less(v, nums[--j]) &amp;&amp; j != l) ;
        <span class="hljs-keyword">if</span> (i &gt;= j)
            <span class="hljs-keyword">break</span>;
        swap(nums, i, j);
    &#125;
    swap(nums, l, j);
    <span class="hljs-keyword">return</span> j;
&#125;</code></pre>
<h3 id="3-性能分析"><a href="#3-性能分析" class="headerlink" title="3.性能分析"></a>3.性能分析</h3><p>快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。</p>
<p>快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 C<sub>N</sub>=2C<sub>N/2</sub>+N，复杂度为 O(NlogN)。</p>
<p>最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N<sup>2</sup>/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。</p>
<h3 id="4-算法改进"><a href="#4-算法改进" class="headerlink" title="4.算法改进"></a>4.算法改进</h3><h4 id="4-1-切换到插入排序"><a href="#4-1-切换到插入排序" class="headerlink" title="4.1 切换到插入排序"></a>4.1 切换到插入排序</h4><p>因为快速排序在小数组中也会递归调用自己，<code>对于小数组，插入排序比快速排序的性能更好</code>，因此在小数组中可以切换到插入排序。</p>
<h4 id="4-2-三数居中"><a href="#4-2-三数居中" class="headerlink" title="4.2 三数居中"></a>4.2 三数居中</h4><p>最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取3个元素，并将大小居中的元素作为切分元素。</p>
<h4 id="4-3-三向切分的快速排序"><a href="#4-3-三向切分的快速排序" class="headerlink" title="4.3 三向切分的快速排序"></a>4.3 三向切分的快速排序</h4><p>对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。</p>
<p>三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ThreeWayQuickSort</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">QuickSort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">protected</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> h)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (h &lt;= l) &#123;
            <span class="hljs-keyword">return</span>;
        &#125;
        <span class="hljs-keyword">int</span> lt = l, i = l + <span class="hljs-number">1</span>, gt = h;
        T v = nums[l];
        <span class="hljs-keyword">while</span> (i &lt;= gt) &#123;
            <span class="hljs-keyword">int</span> cmp = nums[i].compareTo(v);
            <span class="hljs-keyword">if</span> (cmp &lt; <span class="hljs-number">0</span>) &#123;
                swap(nums, lt++, i++);
            &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cmp &gt; <span class="hljs-number">0</span>) &#123;
                swap(nums, i, gt--);
            &#125; <span class="hljs-keyword">else</span> &#123;
                i++;
            &#125;
        &#125;
        sort(nums, l, lt - <span class="hljs-number">1</span>);
        sort(nums, gt + <span class="hljs-number">1</span>, h);
    &#125;
&#125;</code></pre>
<h3 id="5-基于切分的快速选择算法"><a href="#5-基于切分的快速选择算法" class="headerlink" title="5.基于切分的快速选择算法"></a>5.基于切分的快速选择算法</h3><p>快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。</p>
<p>可以利用这个特性找出数组的第 k 个元素。</p>
<p>该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> T <span class="hljs-title">select</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> k)</span> </span>&#123;
    <span class="hljs-keyword">int</span> l = <span class="hljs-number">0</span>, h = nums.length - <span class="hljs-number">1</span>;
    <span class="hljs-keyword">while</span> (h &gt; l) &#123;
        <span class="hljs-keyword">int</span> j = partition(nums, l, h);

        <span class="hljs-keyword">if</span> (j == k) &#123;
            <span class="hljs-keyword">return</span> nums[k];

        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (j &gt; k) &#123;
            h = j - <span class="hljs-number">1</span>;

        &#125; <span class="hljs-keyword">else</span> &#123;
            l = j + <span class="hljs-number">1</span>;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> nums[k];
&#125;</code></pre>

<h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><h3 id="1-堆"><a href="#1-堆" class="headerlink" title="1.堆"></a>1.堆</h3><p>堆中某个节点的值总是大于等于或小于其子节点的值，并且堆是一颗完全二叉树。</p>
<p>堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1.这里不使用数组索引为0的位置，是为了更清晰地描述节点的位置关系。<br><img src="/resource/img/java/Sort_heap.png" srcset="/img/loading.gif"></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Heap</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; </span>&#123;
    
    <span class="hljs-keyword">private</span> T[] heap;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> n = <span class="hljs-number">0</span>;
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Heap</span> <span class="hljs-params">(<span class="hljs-keyword">int</span> maxN)</span> </span>&#123;
        <span class="hljs-keyword">this</span>.heap = (T[]) <span class="hljs-keyword">new</span> Comparable[maxN + <span class="hljs-number">1</span>];
    &#125; 
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> n == <span class="hljs-number">0</span>;
    &#125;
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> n;
    &#125;
    
    <span class="hljs-comment">// 比较：小于返回true；大于等于返回false</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">less</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>&#123;
        <span class="hljs-keyword">return</span> heap[i].compareTo(heap[j]) &lt; <span class="hljs-number">0</span>;
    &#125;
    
    <span class="hljs-comment">// 交换</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">swap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>&#123;
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    &#125;
&#125;</code></pre>

<h3 id="2-上浮和下沉"><a href="#2-上浮和下沉" class="headerlink" title="2.上浮和下沉"></a>2.上浮和下沉</h3><p>在堆中，当一个节点比父节点大，那么需要交换这两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。<br><img src="/resource/img/java/Sort_heap_swim.gif" srcset="/img/loading.gif"></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">swim</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span> </span>&#123;
    <span class="hljs-keyword">while</span> (k &gt; <span class="hljs-number">1</span> &amp;&amp; less(k /<span class="hljs-number">2</span>, k)) &#123;
        swap(k /<span class="hljs-number">2</span>, k);
        k = k /<span class="hljs-number">2</span>;
    &#125;
&#125;</code></pre>
<p>类似的，当一个节点比子节点小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。<br><img src="/resource/img/java/Sort_heap_sink.gif" srcset="/img/loading.gif"></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sink</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span> </span>&#123;
    <span class="hljs-keyword">while</span> (<span class="hljs-number">2</span> * k &lt;= n) &#123;
        <span class="hljs-keyword">int</span> j = <span class="hljs-number">2</span> *k;
        <span class="hljs-keyword">if</span> (j &lt; n &amp;&amp; less(j, j+<span class="hljs-number">1</span>))
            j++;
        <span class="hljs-keyword">if</span> (!less(k, j)) 
            <span class="hljs-keyword">break</span>;
        swap(k, j);
        k = j;
    &#125;
&#125;</code></pre>

<h3 id="3-插入元素"><a href="#3-插入元素" class="headerlink" title="3.插入元素"></a>3.插入元素</h3><p>将新元素放到数组末尾，然后上浮到合适位置。</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(Comparable v)</span> </span>&#123;
    heap[++n] = (T) v;
    swim(n);
&#125;</code></pre>

<h3 id="4-删除最大元素"><a href="#4-删除最大元素" class="headerlink" title="4.删除最大元素"></a>4.删除最大元素</h3><p>从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适位置。</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> T <span class="hljs-title">delMax</span><span class="hljs-params">()</span> </span>&#123;
    T max = heap[<span class="hljs-number">1</span>];
    swap(<span class="hljs-number">1</span>, n--);
    heap[n + <span class="hljs-number">1</span>] = <span class="hljs-keyword">null</span>;
    sink(<span class="hljs-number">1</span>);
    <span class="hljs-keyword">return</span> max;
&#125;</code></pre>

<h3 id="5-堆排序"><a href="#5-堆排序" class="headerlink" title="5.堆排序"></a>5.堆排序</h3><p>把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。</p>
<h4 id="5-1构建堆"><a href="#5-1构建堆" class="headerlink" title="5.1构建堆"></a>5.1构建堆</h4><p>无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。</p>
<h4 id="5-2交换堆顶元素与最后一个元素"><a href="#5-2交换堆顶元素与最后一个元素" class="headerlink" title="5.2交换堆顶元素与最后一个元素"></a>5.2交换堆顶元素与最后一个元素</h4><p>交换之后需要进行下沉操作维持堆的有序状态。</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">HeapSort</span>&lt;<span class="hljs-title">T</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">T</span>&gt;&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">Sort</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;
    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 数组第 0 个位置不能有元素</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(T[] nums)</span> </span>&#123;
        <span class="hljs-keyword">int</span> n = nums.length - <span class="hljs-number">1</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = n / <span class="hljs-number">2</span>; k &gt;= <span class="hljs-number">1</span>; k--)
            sink(nums, k, n);

        <span class="hljs-keyword">while</span> (n &gt; <span class="hljs-number">1</span>) &#123;
            swap(nums, <span class="hljs-number">1</span>, n--);
            sink(nums, <span class="hljs-number">1</span>, n);
        &#125;
    &#125;

    <span class="hljs-comment">// 下沉</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sink</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> k, <span class="hljs-keyword">int</span> n)</span> </span>&#123;
        <span class="hljs-keyword">while</span> (<span class="hljs-number">2</span> * k &lt;= n) &#123;
            <span class="hljs-keyword">int</span> j = <span class="hljs-number">2</span> * k;
            <span class="hljs-keyword">if</span> (j &lt; n &amp;&amp; less(nums, j, j + <span class="hljs-number">1</span>))
                j++;
            <span class="hljs-keyword">if</span> (!less(nums, k, j))
                <span class="hljs-keyword">break</span>;
            swap(nums, k, j);
            k = j;
        &#125;
    &#125;

    <span class="hljs-comment">// 比较：小于返回true；大于等于返回false</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">less</span><span class="hljs-params">(T[] nums, <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>&#123;
        <span class="hljs-keyword">return</span> nums[i].compareTo(nums[j]) &lt; <span class="hljs-number">0</span>;
    &#125;
&#125;</code></pre>

<h3 id="6-分析"><a href="#6-分析" class="headerlink" title="6.分析"></a>6.分析</h3><ul>
<li>一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。</li>
<li>对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。</li>
<li>堆排序是一种原地排序，没有利用额外的空间。</li>
<li>现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。</li>
</ul>
<h2 id="小结"><a href="#小结" class="headerlink" title="小结"></a>小结</h2><h3 id="1-排序算法的比较"><a href="#1-排序算法的比较" class="headerlink" title="1.排序算法的比较"></a>1.排序算法的比较</h3><table>
<thead>
<tr>
<th align="center">算法</th>
<th align="center">稳定性</th>
<th align="center">时间复杂度</th>
<th align="center">空间复杂度</th>
<th align="center">备注</th>
</tr>
</thead>
<tbody><tr>
<td align="center">选择排序</td>
<td align="center">x</td>
<td align="center">N<sup>2</sup></td>
<td align="center">1</td>
<td align="center"></td>
</tr>
<tr>
<td align="center">冒泡排序</td>
<td align="center">&radic;</td>
<td align="center">N<sup>2</sup></td>
<td align="center">1</td>
<td align="center"></td>
</tr>
<tr>
<td align="center">插入排序</td>
<td align="center">&radic;</td>
<td align="center">N ~ N<sup>2</sup></td>
<td align="center">1</td>
<td align="center">时间复杂度和初始顺序有关</td>
</tr>
<tr>
<td align="center">希尔排序</td>
<td align="center">x</td>
<td align="center">N 的若干倍乘于递增序列的长度</td>
<td align="center">1</td>
<td align="center">改进版的插入排序</td>
</tr>
<tr>
<td align="center">快速排序</td>
<td align="center">x</td>
<td align="center">NlogN</td>
<td align="center">logN</td>
<td align="center"></td>
</tr>
<tr>
<td align="center">三向切分的快速排序</td>
<td align="center">x</td>
<td align="center">N ~ NlogN</td>
<td align="center">logN</td>
<td align="center">适用于大量重复元素的数组</td>
</tr>
<tr>
<td align="center">归并排序</td>
<td align="center">&radic;</td>
<td align="center">NlogN</td>
<td align="center">N</td>
<td align="center"></td>
</tr>
<tr>
<td align="center">堆排序</td>
<td align="center">x</td>
<td align="center">NlogN</td>
<td align="center">1</td>
<td align="center">无法利用局部性原理</td>
</tr>
</tbody></table>
<h3 id="2-Java-的排序算法实现"><a href="#2-Java-的排序算法实现" class="headerlink" title="2.Java 的排序算法实现"></a>2.Java 的排序算法实现</h3><p>Java 主要排序方法为 <code>java.util.Arrays.sort()</code>，对原始数据类型使用<font color=#FF000>三向切分的快速排序</font>，对于引用类型使用<font color=#FF000>归并排序</font>。</p>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">基础知识</a>
                    
                      <a class="hover-with-bg" href="/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/tags/%E6%8E%92%E5%BA%8F/">排序</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2020/11/25/java/Vue/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">Vue框架面试总结</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2020/11/20/java/MySQL/">
                        <span class="hidden-mobile">MySQL学习笔记及面试题</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://soldiergit.github.io/" target="_blank" rel="nofollow noopener"><span>Copyright © 2020 soldier Powered by Hexo Fluid Core on Kubernetes</span></a> <i class="iconfont icon-love"></i> <a href="mailto:soldier_wyyx@163.com"><span>联系我</span></a> 
  </div>
  
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


  

  
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "排序算法学习笔记&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>












  
    <!-- Baidu Analytics -->
    <script defer>
      var _hmt = _hmt || [];
      (function () {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?28d1b3a306f2b9f13ed66ffd0d5a0a9a";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>
  

  

  

  
    <!-- Tencent Analytics -->
    <script defer>
      var _mtac = {};
      (function () {
        var mta = document.createElement("script");
        mta.src = "//pingjs.qq.com/h5/stats.js?v2.0.4";
        mta.setAttribute("name", "MTAH5");
        mta.setAttribute("sid", "500732630");
        
        mta.setAttribute("cid", "500732632");
        
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(mta, s);
      })();
    </script>
  

  
    <!-- 51.la Analytics -->
    <script defer type="text/javascript" src="//js.users.51.la/20973747.js"></script>
  

  





</body>
</html>
